package com.mccken.practice.data_structure.data_02;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2023-12-27 15:45
 **/
public class LFUCache implements ILFUCache {
	
	// 记录LFU的最大容量
	private int cap;
	
	// key-value映射，KV表
	private HashMap<Integer, Integer> keyToValue;
	
	// key-frequency映射，KF表
	private HashMap<Integer, Integer> keyToFrequency;
	
	private HashMap<Integer, LinkedHashSet<Integer>> frequencyToKeys;
	
	// 记录最小频率
	int minFreq;
	
	public LFUCache(int capacity) {
		this.cap = capacity;
		this.frequencyToKeys = new HashMap<>();
		this.keyToFrequency = new HashMap<>();
		this.keyToValue = new HashMap<>();
		this.minFreq = 0;
	}

	@Override
	public int get(int key) {
		if (!keyToValue.containsKey(key)) {
			return -1;
		}
		// 增加key的频率
		increaseFrequency(key);
		return keyToValue.get(key);
	}

	@Override
	public void put(int key, int value) {
		if (cap <=0 ) {
			return;	
		}
		
		if(keyToValue.containsKey(key)) {
			keyToValue.put(key, value);
			increaseFrequency(key);
		} else{
			if(cap <= keyToValue.size()) {
				// 容量已满，移除最不常用的key
				removeMinFrequencyKey();
			}
			keyToValue.put(key, value);
			keyToFrequency.put(key, 1);
			frequencyToKeys.putIfAbsent(1, new LinkedHashSet<Integer>());
			frequencyToKeys.get(1).add(key);	
			this.minFreq = 1;
		}
	}

	private void removeMinFrequencyKey() {
		// freq 最小的key列表。根据时序，第一个元素就是最旧的元素了
		LinkedHashSet<Integer> minKeySet = frequencyToKeys.get(minFreq);
		Integer deleteKey = minKeySet.iterator().next();
		minKeySet.remove(deleteKey);
		if (minKeySet.isEmpty()) {
			frequencyToKeys.remove(minFreq);
			// todo 需要更新minFreq吗？
			/**
			 * mccken_mark 实际上没必要更新 minFreq！ 
			 * 因为，minFreq在用法上，是为了在容量已满时候，找到需要淘汰的key。
			 * 淘汰完之后，容量又会空出来了，这时候如果要put元素，插入一个新值时，一定会设置 minFreq = 1
			 */
		}
		keyToValue.remove(deleteKey);
		keyToFrequency.remove(deleteKey);
	}

	private void increaseFrequency(int key) {

		Integer frequency = keyToFrequency.get(key);
		Integer newFrequency = frequency + 1;
		keyToFrequency.put(key, ++frequency);

		LinkedHashSet<Integer> keySet = frequencyToKeys.get(frequency);
		keySet.remove(key);
		if (keySet.isEmpty()) {
			frequencyToKeys.remove(frequency);
			if (minFreq == frequency) {
				minFreq = newFrequency;
			}
		}

		frequencyToKeys.putIfAbsent(newFrequency, new LinkedHashSet<Integer>());
		frequencyToKeys.get(newFrequency).add(key);
	}
}
